In this paper, we first introduce a lower bound technique for the statecomplexity of transformations of automata. Namely we suggest first consideringthe class of full automata in lower bound analysis, and later reducing the sizeof the large alphabet via alphabet substitutions. Then we apply such techniqueto the complementation of nondeterministic \omega-automata, and obtain severallower bound results. Particularly, we prove an \omega((0.76n)^n) lower boundfor B\"uchi complementation, which also holds for almost every complementationor determinization transformation of nondeterministic omega-automata, and provean optimal (\omega(nk))^n lower bound for the complementation of generalizedB\"uchi automata, which holds for Streett automata as well.
展开▼
